package com.leon.algorithm;

import java.util.*;

/**
 * leecode 刷题积累 目标 200题
 *
 * @author leon
 */
public class LeecodeWater {

    /**
     * 两数之和
     */
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> result = new HashMap<>(nums.length - 1);
        result.put(nums[0], 0);
        for (int i = 1; i < nums.length - 1; i++) {
            if (result.containsKey(target - nums[i])) {
                return new int[]{i, result.get(target - nums[i])};
            }
            result.put(nums[i], i);
        }
        return new int[0];
    }

    /**
     * 三数之和
     * 1 暴力解法 三层循环 时间复杂度O(n三次方)
     * 2 排序+双指针 时间复杂度O（n的二次方）
     */
    public List<List<Integer>> threeSum(int[] nums) {
        if (nums.length < 3) {
            return new ArrayList<>();
        }
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<>();
        int length = nums.length;
        for (int i = 0; i < length; i++) {
            if (nums[i] > 0) {
                return result;
            }

            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int left = i + 1;
            int right = length - 1;
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum == 0) {
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[i]);
                    list.add(nums[left]);
                    list.add(nums[right]);
                    result.add(list);
                    while (left < right && nums[left] == nums[left + 1]) {
                        ++left;
                    }
                    while (left < right && nums[right] == nums[right - 1]) {
                        --right;
                    }
                    ++left;
                    --right;
                } else if (sum < 0) {
                    ++left;
                } else {
                    --right;
                }
            }

        }
        return result;
    }

}
